package lc20240613;

import java.util.*;

/**
  * @description 组合总和
  * @author 不知名帅哥
  * @date 2024/6/13 23:17
  * @version 1.0
*/
public class CombinationSum {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        CombinationSum sum = new CombinationSum();
        System.out.println(sum.combinationSum(candidates, target));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        Arrays.sort(candidates);

        backTrack(candidates, target, res, cur, 0);

        for (List<Integer> list : res) {
            Collections.sort(list);
        }
        HashSet<List<Integer>> lists = new HashSet<>(res);
        List<List<Integer>> resList = new ArrayList<>(lists);
        return resList;
    }

    //感觉可能画个图好使一点
    private void backTrack(int[] candidates, int target, List<List<Integer>> res, List<Integer> cur, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(cur));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            cur.add(candidates[i]);
            backTrack(candidates, target, res, cur, sum + candidates[i]);
            cur.remove(cur.size() - 1);
        }
    }
}
